package 剑指II;

/**
 * @description:
 * @author: 小白白
 * @create: 2021-11-25
 **/

public class Jz091粉刷房子 {

    /**
     * 假如有一排房子，共 n 个，每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种，
     * 你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。
     * 当然，因为市场上不同颜色油漆的价格不同，所以房子粉刷成不同颜色的花费成本也是不同的。
     * 每个房子粉刷成不同颜色的花费是以一个 n x 3 的正整数矩阵 costs 来表示的。
     * 例如，costs[0][0] 表示第 0 号房子粉刷成红色的成本花费；costs[1][2] 表示第 1 号房子粉刷成绿色的花费，以此类推。
     * 请计算出粉刷完所有房子最少的花费成本。
     * <p>
     * 示例 1：
     * 输入: costs = [[17,2,17],[16,16,5],[14,3,19]]
     * 输出: 10
     * 解释: 将 0 号房子粉刷成蓝色，1 号房子粉刷成绿色，2 号房子粉刷成蓝色。
     *      最少花费: 2 + 5 + 3 = 10。
     * 示例 2：
     * 输入: costs = [[7,6,2]]
     * 输出: 2
     *  
     * 提示:
     * costs.length == n
     * costs[i].length == 3
     * 1 <= n <= 100
     * 1 <= costs[i][j] <= 20
     */

    public int minCost(int[][] costs) {
        int[][] dp = new int[costs.length][3];

        dp[0] = costs[0];

        for (int i = 1; i < costs.length; i++) {

            for (int j = 0; j < costs[i].length; j++) {

                // 每个颜色的花费都要和上一座房子的另外两个颜色相比
                dp[i][j] = Integer.MAX_VALUE;
                for (int k = 0; k < 3; k++) {
                    if (j == k) {
                        continue;
                    }
                    // 上一层的最少钱 + 当前这一层的钱
                    dp[i][j] = Math.min(dp[i][j], dp[i - 1][k] + costs[i][j]);
                }

            }

        }

        int result = Integer.MAX_VALUE;
        for (int i = 0; i < 3; i++) {
            result = Math.min(result, dp[dp.length - 1][i]);
        }
        return result;
    }

    public static void main(String[] args) {
        Jz091粉刷房子 n = new Jz091粉刷房子();
        int[][] arr = {{6, 4, 3}, {300, 500, 100}, {800, 900, 1}};
        int result = n.minCost(arr);
        System.out.println(result);
    }

}
